package com.kizuki.algorithm.leetcode;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 注意快排的解法
 *
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 */
public class 数组中的第K个最大元素 {

    class Solution {

        // 优先队列实现小顶堆
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> heap = new PriorityQueue<>(k, (a,b) -> a-b);
            for (int i = 0; i < k; i++) {
                heap.offer(nums[i]);
            }
            for(int i = k; i < nums.length; i ++){
                if (heap.peek() < nums[i]) {
                    heap.poll();
                    heap.offer(nums[i]);
                }
            }
            return heap.peek();
        }

        // 基于快排
        public int findKthLargest1(int[] nums, int k) {
            int len = nums.length;
            int left = 0, right = len - 1;
            Random random = new Random();
            while(true) {
                int i = left, j = right;
                int randomIndex = left + random.nextInt(right - left + 1);
                swap(nums, randomIndex, i);
                int value = nums[i];
                while (i < j) {
                    while (i < j && nums[j] >= value) j--;
                    if (i < j) {
                        nums[i++] = nums[j];
                    }
                    while (i < j && nums[i] <= value) i++;
                    if (i < j) {
                        nums[j--] = nums[i];
                    }
                }
                nums[i] = value;
                if (i == len - k) {
                    return nums[i];
                } else if (i > len - k){
                    right = i - 1;
                } else {
                    left = i + 1;
                }
            }
        }

        private void swap(int[] nums, int i ,int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
